#define DEBUG
#include <cstdio>
#include <cstring>
#define INF 0x7ffffff
#define MAXN 100000
#define MAXM 100000
#define MAXLOGN 20

using namespace std;

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

void initSa(int *sa, int *rank, const char *s, int n) {
  static int pos[MAXN+1], temp[MAXN+1], tempr[MAXN+1];
  for (int i=1; i<=n; i++) {
    rank[i] = s[i]-'a';
  }
  for (int i=1; i<=n; i++) {
    pos[rank[i]]++;
  }
  for (int i=1; i<=n; i++) {
    pos[i] += pos[i-1];
  }
  for (int i=n; i>0; i--) {
    sa[pos[rank[i]]]=i;
    pos[rank[i]]--;
  }
  for (int len=1; len<n; len=len*2) {
    for (int i=0; i<=n; i++) {
      pos[i]=0;
    }
    for (int i=1; i<=n; i++) {
      pos[rank[i]]++;
    }
    for (int i=1; i<=n; i++) {
      pos[i] += pos[i-1];
    }

    for (int i=1; i<=n; i++) {
      temp[i]=sa[i];
    }

    for (int i=n; i>0; i--) {
      if (temp[i]-len>0) {
	sa[pos[rank[temp[i]-len]]]=temp[i]-len;
	pos[rank[temp[i]-len]]--;
      }
    }
    for (int i=n-len+1; i<=n; i++) {
      sa[pos[rank[i]]]=i;
      pos[rank[i]]--;
    }
    for (int i=1; i<=n; i++) {
      if (rank[sa[i]]==rank[sa[i-1]] && ((sa[i-1]+len>n && sa[i]+len>n) || ((sa[i]+len<=n && sa[i-1]+len<=n) && rank[sa[i]+len]==rank[sa[i-1]+len]))) {
	tempr[sa[i]] = tempr[sa[i-1]];
      } else {
	tempr[sa[i]] = tempr[sa[i-1]]+1;
      }
    }
    for (int i=1; i<=n; i++) {
      rank[i]=tempr[i];
    }
  }
}

void initHeight(int *height, int *h, const int *sa, const int *rank, const char *s, int n) {
  for (int i=1; i<=n; i++) {
    if (rank[i]==1) {
      h[i]=0;
    } else {
      h[i]=h[i-1]>1 ? h[i-1]-1 : 0;
      for (int j=sa[rank[i]-1]; j+h[i]<=n && i+h[i]<=n && s[i+h[i]]==s[j+h[i]]; h[i]++);
    }
    height[rank[i]]=h[i];
  }
}

void initRMQ(int rmq[][MAXLOGN+1], int *a, int n) {
  for (int i=1; i<=n; i++) {
    rmq[i][0]=a[i];
  }
  for (int j=1; j<=MAXLOGN; j++) {
    for (int i=1; i<=n; i++) {
      if (i+(1<<(j-1))<=n) {
	rmq[i][j] = min(rmq[i][j-1], rmq[i+(1<<(j-1))][j-1]);
      } else {
	rmq[i][j] = rmq[i][j-1];
      }
    }
  }
}

int getLeft(int o, int x, int rmq[][MAXLOGN+1]) {
  int ans=o+1;
  for (int i=MAXLOGN; i>=0; i--) {
    if (o>=(1<<i) && rmq[o-(1<<i)+1][i]>=x) {
      o-=(1<<i);
      ans = o+1;
    }
  }
  return ans;
}

int getRight(int o, int x, int rmq[][MAXLOGN+1], int n) {
  int ans=o-1;
  for (int i=MAXLOGN; i>=0; i--) {
    if (o+(1<<i)-1<=n && rmq[o][i]>=x) {
      o+=(1<<i);
      ans = o-1;
    }
  }
  return ans;
}

class SegmentTree {
public:
  int v[4*MAXN+1];

  int get(int o, int l, int r, int tl, int tr) {
    if (l==tl && r==tr) {
      return v[o];
    } else {
      int mid=(l+r)/2, ret=INF;
      if (tl<=mid && tr>=l) {
	ret = min(ret, get(o*2, l, mid, max(l, tl), min(mid, tr)));
      }
      if (tl<=r && tr>mid) {
	ret = min(ret, get(o*2+1, mid+1, r, max(mid+1, tl), min(r, tr)));
      }
      return ret;
    }
  }

  void set(int o, int l, int r, int t, int tv) {
    if (l==r) {
      v[o]=tv;
    } else {
      int mid=(l+r)/2;
      if (t<=mid) {
	set(o*2, l, mid, t, tv);
      } else {
	set(o*2+1, mid+1, r, t, tv);
      }
      v[o] = min(v[o*2], v[o*2+1]);
    }
  }
};

void sort(int a[][5], int l, int r) {
  int i=l, j=r, mid=a[(l+r)/2][1], temp;
  for (; i<=j; ) {
    for (; a[j][1]>mid; j--);
    for (; a[i][1]<mid; i++);
    if (i<=j) {
      for (int k=0; k<5; k++) {
	temp=a[i][k], a[i][k]=a[j][k], a[j][k]=temp;
      }
      i++, j--;
    }
  }
  if (i<r) {
    sort(a, i, r);
  }
  if (j>l) {
    sort(a, l, j);
  }
}

int main() {
#ifdef DEBUG
  freopen("4614.in", "r", stdin);
  freopen("4614.out", "w", stdout);
#endif

  static char s[MAXN+2];
  static int sa[MAXN+1], rank[MAXN+1], height[MAXN+1], h[MAXN+1], rmq[MAXN+1][MAXLOGN+1], ques[MAXM+1][5], ans[MAXM+1];
  static SegmentTree sgt;
  int n, m;
  scanf("%d %d", &n, &m);
  scanf("%s", s+1);

  initSa(sa, rank, s, n);
  initHeight(height, h, sa, rank, s, n);
  initRMQ(rmq, height, n);
  memset(sgt.v, 127, sizeof(sgt.v));

  for (int i=1; i<=m; i++) {
    scanf("%d %d %d %d", ques[i]+1, ques[i]+2, ques[i]+3, ques[i]+4);
    ques[i][0]=i;
  }
  sort(ques, 1, m);

  for (int i=m, j=n; i>=0; i--) {
    int a=ques[i][1], b=ques[i][2], c=ques[i][3], d=ques[i][4];
    for (; j>=a; j--) {
      sgt.set(1, 1, n, rank[j], j);
    }
    for (int l=1, r=min(b-a+1, d-c+1), mid; l<=r; ) {
      mid = (l+r)/2;
      int tl=getLeft(rank[c], mid, rmq)-1, tr=getRight(rank[c]+1, mid, rmq, n);
      if (sgt.get(1, 1, n, tl, tr)<=b-mid+1) {
	ans[ques[i][0]] = mid;
	l = mid+1;
      } else {
	r = mid-1;
      }
    }
  }

  for (int i=1; i<=m; i++) {
    printf("%d\n", ans[i]);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}
